package q236_lowestCommonAncestor;

import CommonClass.Common.TreeNode;
public class Solution {

    /**
     * 当我们寻找两个节点的公共祖先时，一般希望能够从最下层开始寻找，然后从下向上返回
     * 而后序遍历天然能够满足该条件
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        // 这里最好使用图例来辅助理解
        // 当我们找到了其中一个节点后，其的父节点也就会被反复的返回
        // 而其遇到另一个节点的父节点后 相遇时也就得到了答案节点
        // 此后答案节点的所有父节点都相当于被这个节点覆盖，只会返回答案节点 最后直到root根节点
        // 后序遍历的顺序
        // 左
        TreeNode leftRes = lowestCommonAncestor(root.left, p, q);
        // 右
        TreeNode rightRes = lowestCommonAncestor(root.right, p, q);
        // 中（写操作逻辑）
        if (leftRes != null && rightRes != null) {
            return root;
        }
        if (leftRes != null && rightRes == null) {
            return leftRes;
        }
        if (leftRes == null && rightRes != null) {
            return rightRes;
        }

        // 否则就是两者皆为空
        return null;

    }
}
